package DataStructure.arrayAndList.list.listReverse;

import DataStructure.arrayAndList.list.Nodelj;
import DataStructure.arrayAndList.list.ListReverse;

/**
 * @author liujun
 * @version 1.0
 * @date 2021/12/7
 * @author—Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 利用系统栈 反转链表
 */

public class ListReverseBySystemStack extends ListReverse {
    @Override
    public Nodelj reverse(Nodelj root) {
        if (root == null) {
            return null;
        }
        return reverseByStack(root);
    }

    public Nodelj reverseByStack(Nodelj node) {
        if (node.next == null) {
            return node;
        }
        Nodelj newNode = reverseByStack(node.next);
        // 重建关系
        node.next.next = node;
        node.next = null;
        // 此处需要注意返回值
        return newNode;
    }
}
